import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class Huffman2 {
	
	List alphabet;
	List nodeAlphabet;
	RowPriority2 rowPriority;
	int numberCharacters;
	
	public Huffman2(String string) {
		
		alphabet = new ArrayList();
		nodeAlphabet = new ArrayList();
		rowPriority =  new RowPriority2(string.toUpperCase());
		numberCharacters = rowPriority.size();
		
		for (int i = 0; i < numberCharacters-1; i++) {
			NodeH2 z;
			NodeH2 x = rowPriority.extractMin();
			NodeH2 y = rowPriority.extractMin();
			z = new NodeH2("", x.getFrequency() + y.getFrequency());
			z.setLeft(x);
			z.setRight(y);
			rowPriority.insert(z);
		}

		
	}

	private void makeCodeWord(NodeH2 nodeMinor, String codeWord) {
		
		String aux1, aux2;
		
		if (nodeMinor!=null) {
			
			aux1 = codeWord;
			aux2 = nodeMinor.character;

			if (!nodeMinor.character.equals("")) {
				alphabet.add(nodeMinor.character);
				nodeAlphabet.add(nodeMinor);
				nodeMinor.codeWord = codeWord;
				
				aux1 = codeWord;
				aux2 = codeWord;
			}
			makeCodeWord(nodeMinor.getLeft(), nodeMinor.codeWord + "0");
			makeCodeWord(nodeMinor.getRight(), nodeMinor.codeWord + "1");
		}
	}
	
	private NodeH2 seachNode(String string) {
		NodeH2 node;
		for (int i=0; i<numberCharacters; i++) {
			node = (NodeH2) nodeAlphabet.get(i);
			if (node.character.equals(string)) return node;
		}
		return null;
	}

	public String toString() {
		String string = "";
		
		makeCodeWord(rowPriority.getMinor(), "");
		Collections.sort(alphabet);
		NodeH2 node;
		for (int i=0; i<numberCharacters; i++) {
			node = seachNode((String)alphabet.get(i));
			string += node.character + " " + node.codeWord + " ";
		}
		
		
		return string;
		
	}

}
